//
//  main.m
//  CycleChain
//
//  Created by XAJZ on 2020/4/3.
//  Copyright © 2020 XAJZ. All rights reserved.
//

//此工程主要演示单向循环链表

#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"

/* 存储空间初始分配量 */
#define MAXSIZE 20

#define SUCCESS 1
#define ERROR 0

#define TRUE 1
#define FALSE 0

//表内元素的类型 假设为 int
typedef int ItemType;
//返回各个函数的操作码
typedef int Status;

//链式表的节点定义
typedef struct Node{
//    数据域
    ItemType data;
//    指针域
    struct Node *next;
}Node;

typedef struct Node* List;


/*
4.1 循环链表创建!
2种情况:① 第一次开始创建; ②已经创建,往里面新增数据

1. 判断是否第一次创建链表
   YES->创建一个新结点,并使得新结点的next 指向自身; (*L)->next = (*L);
   NO-> 找链表尾结点,将尾结点的next = 新结点. 新结点的next = (*L);
*/
Status createCycleChain(List *l){
    int itemValue;
    List temp = NULL;
//    循环遍历用来找尾
    List key = NULL;
//    每一次操作用来记录尾
//    List tail = NULL;
    printf("输入节点的值，输入0结束：\n");
    while (1) {
        scanf("%d", &itemValue);
        if (itemValue == 0) break;
        

        if (*l == NULL) {
//        如果链表为空，创建新的节点作为新链表的起始节点，next 要指向自己
            *l = (List)malloc(sizeof(Node));
            
            if (!l) exit(ERROR);
            (*l)->data = itemValue;
            (*l)->next = *l;
//            tail = *l;
        }else{
//            如果链表不为空，需要找到链表的尾，将新的数据插入作为新的尾，并使其next指向头。
//            找尾有两种方法：
//            1.循环遍历，若某节点的next指向头，那么它就是尾 2.每一次操作的时候将尾记录下来。
            for (key = *l; key->next != *l; key = key->next) ;
            
//            创建新的节点
            temp = (List)malloc(sizeof(Node));
            temp->data = itemValue;
            temp->next = *l;
            key->next = temp;
            
//            temp->data = itemValue;
//            temp->next = *l;
//            tail->next = temp;
//            tail = temp;
        }
    }
    return SUCCESS;
}


//4.2 遍历循环链表，循环链表的遍历最好用do while语句，因为头节点就有值

/// 遍历循环链表
/// @param l 链表
Status printCycleChain(List l){
    
    if (!l) {
        return ERROR;
    }else{
        List t;
        t = l;
        printf("链表信息\n");
        do {
            printf("%d, ", t->data);
            t = t->next;
        } while (t != l); // 若当前节点为头，说明已经打印完毕
        printf("\n");
    }
    return SUCCESS;
}


/// 在指定位置为链表插入新的结点
/// @param l 链表
/// @param index 位置
/// @param value 新的值
Status chainInsert(List *l, int index, int value){
    
    List temp;
    
    temp = (List)malloc(sizeof(Node));
    if (!temp) {
        return ERROR;
    }
    temp->data = value;
    
    //    如果插入位置为首元结点，需要特殊处理：
    //    1.创建新的结点 temp, 新结点指向原来的头 ；
    //    2.原来的尾结点指向新的结点；
    //    3.将新结点变为新的头。
    if (index == 1) {
        List tail;
        for (tail = *l; tail->next != *l; tail = tail->next) ;
        
        temp->next = *l;
        tail->next = temp;
        *l = temp;
    }else{
    //    如果插入位置不是首元：（注意如果超出位置，就放在最后一个结点上）
    //    1.创建新的结点 temp, 找到插入位置的前置结点，新的结点 指向 前置结点的下一个结点；
    //    2.前置结点指向新节点；
        int i;
        List front; // 前置结点
        for(i = 1, front = *l; front->next != *l && i != index - 1; front = front->next, i++) ;
        
        if (i != index - 1) {
             printf("没找到正确位置!\n");
            return ERROR;
        }
        
        temp->next = front->next;
        front->next = temp;
        
    }
    return SUCCESS;
}


/// 删除链表特定位置的结点
/// @param l 链表
/// @param index 删除位置
/// @param value 带回删除结点的值
Status chainDelete(List *l, int index, int *value){
    List temp;
    
    if (!l) {
        return ERROR;
    }
    
//    如果删除的是首元，需要做特殊操作：
//    1.使用temp指针标记首元结点，找寻尾结点；
//    2.尾结点指向temp的下一个结点；
//    3.使temp的下一个结点成为链表的头；
//    4.带回temp的值，释放temp.
    if (index == 1) {
        temp = *l;
        
        // 若链表只有一个元素了，那就 删除，释放头结点，将链表置空。
        if (temp->next == *l) {
            *value = temp->data;
            free(temp);
            *l = NULL;
            return SUCCESS;
        }
        
        List tail;
        
        for (tail = *l; tail->next != *l; tail = tail->next) ;
    
        tail->next = temp->next;
        *l = temp->next;
        *value = temp->data;
        free(temp);
        
    }else{
//        若删除的不是链表的首元结点：
//        1.找到删除结点的前置结点 front，使用 temp 标记 front 的下一个结点，它就是需要删除的结点；
//        2.使前置结指向temp的下一个结点；
//        3.删除并释放temp结点。
        List front;
        int i;
        
        for (i = 1, front = *l; front->next != *l && i != index - 1; front = front->next, i++) ;
        
        if (i != index - 1) {
            printf("没找到正确位置!\n");
            return ERROR;
        }
        
        temp = front->next;
        front->next = temp->next;
        *value = temp->data;
        free(temp);
        
    }
    return SUCCESS;
}


/// 查找链表特定位置结点的值
/// @param l 链表
/// @param index 位置
/// @param value 带回找到的值
Status chainGet(List l, int index, int *value){
    if (!l) {
        return ERROR;
    }
    List temp;
    int i;
    for (temp = l,i = 1; i < index && temp->next != l; temp = temp->next, i++) ;
    
    if (temp == l) {
//        根本就没有进入循环，只赋值了初始条件，确认是不是就是找的第一个元素
        if (index == 1) {
            *value = temp->data;
            return SUCCESS;
        }
    }else{
        if (temp->next == l && i != index) {
//           循环结束了而且找到了最后一个元素，确认是不是要找的元素
            return ERROR;
        }else{
//           在中间就结束了循环，那一定是找到了
            
//        带回记录值
           *value = temp->data;
           return SUCCESS;
        }

    }
    return ERROR;
}


int main(int argc, const char * argv[]){
    printf("循环链表学习开始！\n");
    
    
    List l;
    int p, num;
    int iStatus;
    
    if (createCycleChain(&l)) printCycleChain(l);
    
    chainInsert(&l, 11, 99);
    printf("插入后链表为：\n");
    printCycleChain(l);
    
    chainDelete(&l, 11, &num);
    printf("删除的元素为：%d\n 删除后链表为：\n", num);
    printCycleChain(l);
    
    
    if(chainGet(l, 1, &num)){
        printf("找到了： %d ", num);
    }else{
        printf("没找到");
    }
    
    if(chainGet(l, 2, &num)){
           printf("找到了： %d ", num);
       }else{
           printf("没找到");
       }

    if(chainGet(l, 10, &num)){
        printf("找到了： %d ", num);
    }else{
        printf("没找到");
    }
    
    if(chainGet(l, 100, &num)){
        printf("找到了： %d ", num);
    }else{
        printf("没找到");
    }
   
}


